package com.ljy.my_study.lintcode.最前缺少的正数;

import java.util.HashSet;
import java.util.Set;

/**
 * @author James
 * @date 2019年5月8日
 */
public class TestMain {
	// Given an unsorted integer array, find the first missing positive integer.
	// Have you met this question in a real interview? Yes
	// Problem Correction
	// Example
	// Example 1:
	//
	// Input:[1,2,0]
	// Output:3
	// Example 2:
	//
	// Input:[3,4,-1,1]
	// Output:2

	public static void main(String[] args) {
		int[] A= {3,4,-1,1};
		System.out.println(firstMissingPositive(A));
	}

	public static int firstMissingPositive(int[] A) {
		Set<Integer> set=new HashSet<>();
		int min=1;
		for(int a:A) {
			set.add(a);
			while(set.contains(min)) min++;
		}
		return min;
	}
}
